package com.example.demo.leetcode;

/**
 * 链接：<a href="https://leetcode.cn/problems/minimum-size-subarray-sum/description/?envType=study-plan-v2&envId=top-interview-150">https://leetcode.cn/problems/minimum-size-subarray-sum/description/?envType=study-plan-v2&envId=top-interview-150</a><br>
 * 给定一个含有 n 个正整数的数组和一个正整数 target 。 <br>
 * 找出该数组中满足其总和大于等于 target 的长度最小的 连续子数组。<br>
 * 并返回其长度。如果不存在符合条件的子数组，返回 0 。<br>
 * <p>
 * <p>
 * 示例 1：<br>
 * <p>
 * 输入：target = 7, nums = [2,3,1,2,4,3]<br>
 * 输出：2<br>
 * 解释：子数组 [4,3] 是该条件下的长度最小的子数组。<br>
 * 示例 2：<br>
 * <p>
 * 输入：target = 4, nums = [1,4,4]<br>
 * 输出：1<br>
 * 示例 3：<br>
 * <p>
 * 输入：target = 11, nums = [1,1,1,1,1,1,1,1]<br>
 * 输出：0<br>
 */
public class _209_长度最小的子数组 {

    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 4, 5};
        int i = new Solution().minSubArrayLen(11, nums);
        System.out.println(i);
    }

    public static class Solution {
        /**
         * 使用滑动窗口的方式
         * 时间复杂度：O(n),最大的时间复杂度是O(n+n),即是i和j都遍历1遍。
         * 精简复杂度：O(1)
         */
        public int minSubArrayLen(int target, int[] nums) {
            int i = 0, j = 0;
            int tatal = nums[i];
            int min = Integer.MAX_VALUE;
            while (true) {
                //total小于target时，j继续加1，并且total加上nums[j]
                if (tatal < target) {
                    if (++j >= nums.length) {
                        break;
                    }
                    tatal += nums[j];
                }
                //total大于等于target时，i减一1，并且total减去nums[i]
                if (tatal >= target) {
                    min = Math.min(min, j - i + 1);
                    tatal -= nums[i];
                    if (++i >= nums.length) {
                        break;
                    }
                }
            }
            return min == Integer.MAX_VALUE ? 0 : min;
        }

        /**
         * 暴力法
         * 时间复杂度：O(n^2)，其中 n 是数组的长度。需要遍历每个下标作为子数组的开始下标，对于每个开始下标，需要遍历其后面的下标得到长度最小的子数组。
         * 空间复杂度：O(1)。
         */
        public int minSubArrayLen1(int target, int[] nums) {
            int n = nums.length;
            if (n == 0) {
                return 0;
            }
            int ans = Integer.MAX_VALUE;
            for (int i = 0; i < n; i++) {
                int sum = 0;
                for (int j = i; j < n; j++) {
                    sum += nums[j];
                    if (sum >= target) {
                        ans = Math.min(ans, j - i + 1);
                        break;
                    }
                }
            }
            return ans == Integer.MAX_VALUE ? 0 : ans;
        }
    }
}
